package Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}16:20
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {1,5,9,15,66,879,154,10};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        //首先确定最大数的长度
        int max = 0;
        for (int i = 0; i < arr.length; i++){
            if (max <= arr[i]){
                max = arr[i];
            }
        }
        int length = (max+"").length();

        //开始进行桶的初始化
        int[][] Radix = new int[10][arr.length];
        int[] RadixHeight = new int[10];

        //开始遍历插入
        for (int i = 0,n = 1; i < length; i++,n*=10){//n表示现在的位数
            //计算出每个数的当前指定位数的值

            //在桶中进行对应的存储
            for (int x = 0; x < arr.length;x++ ) {
                int index = arr[x]/n%10;
                Radix[index][RadixHeight[index]] = arr[x];
                RadixHeight[index]++;
            }

            //下面进行读取 从位数1-10的顺序读取、读取完后将高度初始化回0
            int x = 0;
            for (int a = 0; a < 10;a++) {
                if (RadixHeight[a]!=0) {
                    for (int j = 0; j < RadixHeight[a]; j++) {
                        arr[x] = Radix[a][j];
                        x++;
                    }
                }
                RadixHeight[a] = 0;
            }
        }
    }
}
